All the problems are in minimization here, i.e. if an objective function \(z(x)\) is actually in maximisation, we will minimise \(-z(x)\) instead. Only binary variables are considered here.

1 Research questions

The first purpose of this study is to learn how some components of the branch and bound influences the behaviour of the algorithm it terms of computational time (expressed in seconds everywhere) and in term of number of nodes explored (i.e. how much nodes are developed in the branch and bound tree before the algorithm ends).

The branch and bound algorithm will always use the linear relaxation as lower bound set and the incumbent set as upper bound set. At each nodes, the extreme points of the lower bound set are checked for integrality and possibly added to the upper bound set. The components that will vary are:

The second purpose of this study is to learn how the caracteristics of an instance can affect its difficulty. The difficulty will be here mesured by the size of the non-dominated set, and the computational time required to solve the instance. The computational time will be determined using the branch and bound algorithm previously described. Note that the complexity of an objective space search algorithm is positively correlated to the size of the non-dominated set as the more non-dominated there are, the more integer programs have to be solved.

The focus will be here on the objective function coefficients. The first research question here is: does the range of the objective function coefficient has an impact on the difficulty of the problem ?. In order to answer that, three different ranges will be tested:

For the facility location problems, two sets of costs (i.e. coefficients of objective function) can be identified: the assignment costs (\(c_{ij}\)) and the facility opening costs (\(f_j\)). It is reasonable to assume that these two sets of costs may not take their values in the same range. Let the assignment costs take their values in \([a,b]\), the generation of the facility opening costs will be divided into two categories of instances:

The second research question related to that topic is: does the method used to generate the coefficients of the objective function has an impact on the difficulty of the problem ?. Indeed, the usual procedure to generate objective function is to generate the coefficients randomly in a given range \([a,b]\). However, one could imagine other way to generate coefficient. Four methods will be studied here.

You must enable Javascript to view this page properly.

You must enable Javascript to view this page properly.

You must enable Javascript to view this page properly.

You must enable Javascript to view this page properly.

2 Instances

List of test instances.

Go to instance example

Several methods for generating the coefficient of the objective functions are tested here. This is given by the column coef.

3 Preliminary tests CPU time

Here are tested different combinations of variable and node selection for the basic branch and bound. In the following :

3.1 Random coefficient generation

The coefficient are generated using the random method.

3.1.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

3.1.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

3.1.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

3.1.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.1.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2 Sphere Down coefficient generation

The coefficient are generated using the spheredown method.

3.2.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

3.2.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

3.2.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

3.2.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.2.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3 Sphere Up coefficient generation

The coefficient are generated using the sphereup method.

3.3.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

3.3.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

3.3.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

3.3.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.3.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4 Two boxes coefficient generation

The coefficient are generated using the random method.

3.4.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

3.4.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

3.4.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

3.4.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

3.4.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4 Study on the coefficients of the objective function

In this section, relations between |YN| and various characteristics of the coefficient of the objective function are studied.

4.1 Knapsack

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

4.2 Assignment

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

4.3 Facility location easy

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

4.4 Facility location hard

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

end